#!/usr/bin/python

import math

sieve_list=[]

def Create_Sieve(n):
	'''
	This function creates a "Sieve" of a given number n. A Sieve, in this sense, is a 'list' that contains all numbers up to the floored value of the square root of the given number. Then it will go through and remove non-prime numbers, also known as composite numbers.
	'''
	k=2
	flsqn=0
	#print "VALUE OF N: ", n
	sqn=math.sqrt(n)
	flsqn=math.floor(sqn)
	while k <= flsqn:
		sieve_list.append(k)
		k+=1
	
	c=0
	m=0
	while c < len(sieve_list):
		k=sieve_list[c]
		#print "value of k:",k
		m=c+1
		#print "m, before m-while look:", m
		if sieve_list[c]**2 < sieve_list[-1]:
			while m < len(sieve_list):
				#m=c
				#print "value of sieve_list[m]:",sieve_list[m]
				if sieve_list[m] % k == 0:
					del sieve_list[m]
				m+=1
		else:
			break
		c+=1
	return sieve_list
	#print "Generated Sieve_List"

def Is_Prime(k):
	'''
	This function will was the sieve from the 'Create_Sieve' function to determine if a given number, k, is a prime number.
	'''

	result=Create_Sieve(k)
	v=0
	while v < len(result):
		if k % result[v] == 0:
			return False
		v+=1
	return True
			
if __name__ == '__main__':
	#num=raw_input("What number do you want to test? (To see if it is a prime?): ")
	num=1746860020068409
	#num=13091204281
	#num=982451653
	#num=119218851371
	num=int(num)
	#print Is_Prime(num)
	#new_list=Create_Sieve(num)
	#print new_list
	#print "Size of list:",len(new_list)
	#if Create_Sieve(num) == True:
	#	print "\nThe number, ", num, " is a prime number!"
	#else:	
	#	print "\nThe number, ", num, " is a composite number!"

	print "Create_Sieve: ", Create_Sieve(num)
	print "Is_Prime: ", Is_Prime(num)
	#print Is_Prime(num)
